The present invention relates to Range Content Addressable Memory and, more particularly, to a system for, and method of, implementing a RAM-Based Range Content Addressable Memory.
Conventional memory arrays such as Random Access Memories (RAMs) store and retrieve data units indexed by their address.
Content Addressable Memories (CAMs), on the other hand, are associative memories that contain Key Entries and Associated Data Entries that uniquely correspond to the Key Entries. A CAM stores the key entries and the associated data entries at any available location and retrieves the Associated Data for any key that is submitted to be searched in the CAM.
Associative fast operation requires parallelism, such that the Submitted Key is searched concurrently in all CAM location. This requires the incorporation of comparators in each memory cell (see, for example, M. D. Pepler, et al., “Dataflow Token Matching Using Pipelined Content Addressable Memory”, May 1998, http://www.elec-eng.leeds.ac.uk/pgrad/eenmdp/paperl.html; R. E. Hodson, et al, “CNU/CEBAF/NASA Collaboration, Content Addressable Memory (CAM)”, http://www.pcs.cnu.edu/˜rhodson/cam/camPage.html; Chuang, et al, U.S. Pat. No. 4,928,260), which makes a CAM cell bigger and slower in comparison to a RAM cell. Consequently, CAM chips are usually expensive, and are also characterized by small memory capacity (see “Netlogic Microsystems Introduces Family of Content Addressable Memory Products for Network Systems”, Netlogic Microsystems Inc., Aug. 24, 1998.).
Attempts to use software to make RAMs operate in an associative manner lead to speed limitations, since each associative reference typically requires many RAM accesses and many processor cycles. Nevertheless, for many applications, processor and RAM speed improvements have kept pace with application speed requirements. In many more natural CAM applications, especially those that require massive amounts of memory, CAM implementation has not been successful due to the lack of fast, dense and inexpensive CAMs.
In spite of its limitations, CAMs have been utilized in the communications industry, because a RAM with a software shell cannot achieve the speed required for an associative lookup. Despite the recent major improvements made in the CAM density and speed (see Netlogic Application Note NCS01: “How CAMs Ease Router-Table Designs”, Revision 1.1; SiberCore Technologies: SiberCAM™ Family Large Capacity Content Addressable Memory Feature List”, April 1999; UTMC Microelectronic Systems: “UTCAM Engine™ LPM”, November 1988), the inherent density problems coupled with the high cost have limited the use of the CAMs to the most speed-critical applications, such as routing and switching in data communications.
U.S. Pat. No. 4,928,260 to Chuang, et al., among others (e.g., J. Postel: “Internet Protocol”, September 1981, IETF, RFC 0760; V. Fuller, et al., “Classless Inter-Domain Routing”, IETF, RFC 1519, June 1993; Karanjit S. Siyan, “Inside TCP/IP, A Comprehensive Introduction to Protocols and Concepts”, New Riders Publishing, 1997) disclose that the main drawback of modern CAMs lies in the design of the CAM basic cell circuit, due to the limitations of the cell packing and performance.
One approach was to build a much bigger RAM-based CAM system using RAM technology (see UTMC Microelectronic Systems: “UTCAM Engine™ LPM”, November 1988). However, this CAM system is of mediocre performance due to the limitations imposed by the RAM components, specifically by their limited bus bandwidth.
Another approach, disclosed by U.S. Pat. No. 5,949,696, utilizes a dynamic CAM, in which each cell contains a comparator connected to the match line output. The match line output outputs first and second logic states in response to different and similar logic states, respectively. The CAM cell also includes a first storage element having an input connected to a first data input line, and an output connected to the comparator, a second storage element having an input connected to a second data input line, and an output connected to an input of the comparator. The cell stores masked states by storing similar logic states in both storage elements. Isolation between the match line output and the storage elements is obtained by eliminating direct connection between the match line output and the storage elements.
U.S. Pat. No. 4,791,606 discloses a dynamic CAM having N and P channel transistors aligned in stripes for providing dense packing. Each cell includes an XOR-gate for comparing a stored data bit with a comparand bit. Each pair of neighboring rows and each pair of neighboring columns is arranged symmetrically, for improving the packing density.
U.S. Pat. No. 5,383,146 discloses a memory array that is partitioned into CAM and RAM subfields by disabling the comparator in each memory cell in the selected column of CAM cells to create RAM-functioning cells. The comparators in the RAM-functioning cells can be re-enabled, so that these cells may participate in subsequent comparisons to a search word. This arrangement allows direct retrieval and storage of associated data in RAM-functioning cells that correspond to data words that are determined to match a given search word.
It must be emphasized that the CAM cells disclosed in the above-referenced patents are still relatively complex and occupy large areas in comparison with RAM cells of similar technology. The cited prior art does not enable the implementation of a fast, dense, high-capacity, power-efficient and inexpensive CAMs using RAM-based technology.
A successful approach to utilizing RAM-based technology on a binary CAM is provided in my co-pending, unpublished (and as such, is not to be construed as prior art with regard to the present application) PCT Patent Application Ser. No. IL01/00458, which is incorporated by reference for all purposes as if fully set forth herein. A method and apparatus are disclosed therein for the high-rate arrangement, storage and extraction of data in a two-dimensional memory array. The two-dimensional array, which consists of memory cells, is arranged in rows and columns, each of the key entries in these cells having a unique pair of indices that indicate the key entry location in the array. The associated data entries that correspond to these key entries are stored in another two-dimensional array under the same pair of indices. When a submitted key is searched and found, the associated data is retrieved from the corresponding cell in the other two-dimensional associated-data memory array and a match signal, “True” or “False”, is also output with the retrieved associated data entry to indicates whether the associated data is valid or not. The entries in each two-dimensional array are arranged, each entry in a separate cell, in rows or columns, in a subsequent ascending or descending order. The entries are arranged in the array so that at least a portion of the array is filled without blanks with valid entries. The key and associated data entries are arranged and stored in the arrays prior to submission of a key for search.
The main innovations introduced by these devices are:                Surrounding the RAM structure with search logic in the RAM periphery: The number of comparator units is proportional to the RAM periphery length rather than to the RAM area. This results in dramatic savings in the amount of comparator logic, while keeping the memory cell extremely efficient in density and speed. The CAM implementation overhead is typically less than 15%. Therefore, the CAM density obtained with this method is asymptotically close to the comparable size in RAM technology.        Fast Search Algorithm: The surrounding logic in conjunction with the RAM structure performs searches with the same throughput as a comparable RAM, and twice the latency. (Theoretically, single clock latency may be accomplished, but pipelining may yield a better throughput and a similar latency if measured on absolute time scale (nano-seconds).        Continuous “Housekeeping” Procedure: Unlike CAMs of the prior art, these CAM devices keep the “house in order”. That is, the deletion of keys does not leave “holes” in the list, which would otherwise require “housekeeping” operations on the managing processor section. Similarly, the addition of new keys keeps the list in a perfect sequence. This “housekeeping” procedure takes longer than the search, but is much faster than required by the system. The overhead associated with the Key List update is significantly shorter when compared with the time taken by the processor to do the housekeeping. This superior performance is due to the efficient RAM and Insert/Remove hardware architecture, which execute very time-efficient algorithms.        